package com.future;

import com.future.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * Description: 515. 在每个树行中找最大值
 *
 * @author weiruibai.vendor
 * Date: 2023/1/10 09:31
 */
public class Solution_515 {

    private static Solution_515 instance = new Solution_515();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(5);

        TreeNode node3 = new TreeNode(3);
        root.left.right = node3;

        node3.left = new TreeNode(100);
        /*node3.left.left = new TreeNode(200);
        node3.left.left.right = new TreeNode(300);*/

        root.right = new TreeNode(2);
        root.right.right = new TreeNode(9);
       /* root.right.right.left = new TreeNode(100);
        root.right.right.left.right = new TreeNode(100);*/
        // [10,5,15,null,null,6,20]
        System.out.println(instance.largestValues(root));
        System.out.println();
        instance.layerSearch(root);
    }

    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<TreeNode> linked = new LinkedList<>();
        TreeNode nextLayerNode = root;
        TreeNode curNode;
        linked.push(root);
        /**
         * 保存当前层的节点，方便回溯找到前一个非空节点的下一层！！
         */
        Stack<TreeNode> stack = new Stack<>();
        int maxValue = Integer.MIN_VALUE;
        while (!linked.isEmpty()) {
            curNode = linked.pollFirst();
            stack.add(curNode);
            maxValue = Math.max(maxValue, curNode.val);
            if (curNode == nextLayerNode) {
                nextLayerNode = null != curNode.right ? curNode.right : curNode.left;
                if (nextLayerNode == null) {
                    /**
                     * 回溯找到前一个非空节点的下一层
                     */
                    while (!stack.isEmpty() && nextLayerNode == null) {
                        TreeNode pop = stack.pop();
                        nextLayerNode = pop.right != null ? pop.right : pop.left;
                    }
                }
                ans.add(maxValue);
                maxValue = Integer.MIN_VALUE;
                stack.clear();
            }
            if (curNode.left != null) {
                linked.addLast(curNode.left);
            }
            if (curNode.right != null) {
                linked.addLast(curNode.right);
            }
        }
        return ans;
    }

    /**
     * 层级遍历
     *
     * @param root
     */
    public void layerSearch(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> linked = new LinkedList<>();
        TreeNode nextLayerNode = root;
        TreeNode curNode;
        linked.push(root);
        Stack<TreeNode> stack = new Stack<>();
        while (!linked.isEmpty()) {
            curNode = linked.pollFirst();
            list.add(curNode.val);
            stack.add(curNode);
            if (curNode == nextLayerNode) {
                nextLayerNode = null != curNode.right ? curNode.right : curNode.left;
                if (nextLayerNode == null) {
                    while (!stack.isEmpty() && nextLayerNode == null) {
                        TreeNode pop = stack.pop();
                        nextLayerNode = pop.right != null ? pop.right : pop.left;
                    }
                }
                System.out.println(list);
                list.clear();
                stack.clear();
            }
            if (curNode.left != null) {
                linked.addLast(curNode.left);
            }

            if (curNode.right != null) {
                linked.addLast(curNode.right);
            }
        }
    }

}
